试题四(共15分)

凸多边形是指多边形的任意两点的连线均落在多边形的边界或者内部。相邻的点连线落在多边形边上，称为边，不相邻的点连线落在多边形内部。称为弦。假设任意两点连线上均有权重，凸多边形最优三帮剂分问题定义为：求将凸多边形划分为不相交的三角形集合，且各三角形权重之和最小的剖分方案。每个三角形的权重为三条边权重之和。

假设N个点的凸多边形点编号为V1,V2,……,VN,若在VK处将原凸多边形划分为一个三角形V1VkVN，两个子多边形V1,V2,…,Vk和Vk,Vk+1,…VN，得到一个最优的剖分方案，则该最优剖分方案应该包含这两个子凸边形的最优剖分方案。用m[i][j]表示带你Vi-1,Vi,…Vj构成的凸多边形的最优剖分方案的权重，S[i][j]记录剖分该凸多边形的k值。

则

其中，w(V-1x)=W-1.k+W4./+Wj,.1-1为三角形V,-1VV,的权重，W1-1,k,Wk,j,Wj.1-1分别

为该三角形三条边的权重。

求解凸多边形的最优剖分方案，即求解最小剖分的权重及对应的三角形集。

#include

#define N 6

/* 凸多边形规模 */

int m[N + 1] [N + 1];   /* m[i][j]表示多边形Vi-1到Vj最优三角剖分的权值 */

int S[N + 1] [N + 1];   /* S[i][j]记录多边形Vi-1 到Vj最优三角剖分的k值 */

int W[N + 1] [N + 1];   /* 凸多边形的权重矩阵，在main函数中输入 */

/*三角形的权重a，b，c，三角形的顶点下标*/

int get_ triangle_weight( int a int b int c )
{
	return(W[a][b] + W[b][c] + W[c][a]);
}


/*求解最优值*/

void triangle_partition()
{
	int i, r, k, j;

	int temp;

  /*初始化*/
	for ( i = 1; i <= N; i++ )
	{
		m[i][i] = 0;
	}

  /*自底向上计算m，S*/
	for ( r = 2; (1); r++ )
	{ 
    /*r为子问题规模*/
    /* r<=N */
		for ( i = 1; k <= N - r + 1; i++ )
		{
			(2);                                                                    
      /* int j=i+r-1 */
			m[i][j] = m[i][j] + m[i + 1][j] + get_triangle_weight( i - 1, i, j );   
      
      /*k=j*/
			S[i][j] = i;

			for ( k = j + 1; k

        temp = m[i][k] + m[k + 1][j] + ge_triangle_ weight( i - 1, k, j );

        if ( (3) )
        { /*判断是否最小值*/ /* temp */
          m[i][j] = temp;

          S[i][j] = k;
        }
      }
    }
  }
}

/*输出剖分的三角形i，j：凸多边形的起始点下标*/
void print_triangle( int i, int j )
{
  if ( i == j )
    return;

  print_triangle( i, S[i][j] );

  print_triangle( (4) ); /* s[i][j]+1,j */

  print( " V % d - -V % d --V % d \ n ", i - 1, S[i][j], j );
}